In many data processing applications, it is often desirable to encode a data stream using trellis codes or other data encoding techniques. Trellis codes are a general class of convolutional codes in which state transitions may be diagrammed in the form of a trellis, but which do not necessarily exhibit shift register-like characteristics. For example, in digital communication systems, trellis coding of modulation data, when combined with an appropriate mapping of the encoded data to a transmitted signal set, can improve the performance of a receiver without an increase in transmitted signal power or bandwidth. The equivalent signal-to-noise improvement attributable to data encoding is referred to as coding gain, and results in increased bandwidth and power efficiency.
As a result, Trellis decoders are included in many products including modems, cellular phones, and satellite receivers. These applications are relatively slow-speed, however, compared with the demands of digital video data streams, which require decoding at a rate of 10 MHz or greater.
A convolutional encoder is a finite state machine in which evolution is controlled by the succession of bits in the message. For each coding cycle, information is generated by the encoder concerning the evolution of its internal state. The decoder searches for the most likely evolution of the encoder as a function of the arriving information. An example of an encoder is a simple shift register of length .upsilon., which receives the bits u.sub.0, u.sub.1, . . . , u.sub.n to be transmitted. The contents of the .upsilon. registers represents the 2.sup..upsilon. possible states. The succession of encoder states is usually represented by a path in the transition diagram (trellis) of the encoder as shown in FIG. 1. FIG. 1 shows an example of a trellis for .upsilon.=2. The bold path indicates the succession of encoder states at times t=0 to 5. The message bit which changes the encoder state between t=i and t=i+1 is indicated on the corresponding branch. For example, the arrival of a "1" in the shift register changes the state of the encoder at t=1, 01, to 10 at t=2.
At each decoding cycle, the decoder receives information on the encoder transition. The most likely previous state among the 2.sup..upsilon. possible states is usually determined by the branch metric unit and by the Add/Compare/Select (ACS) unit. Each node of the trellis is associated with a path called the "surviving path." All surviving paths are converging towards a unique path provided that the number of successive branches is equal to or greater than a convergence length L. This unique path is the decoded message.
One technique for managing the surviving memory is called "traceback." A node is chosen at random and its surviving path is followed on a depth of L+H in order to obtain H decoded states. The main advantage of traceback is the very dense storage of the decision vectors in memories. Disadvantages include a large decoding delay as well as having to store a large number of decision vectors.
Existing Trellis decoders have at least three problems when used in connection with very fast real-time data streams such as video information, which this invention addresses:
1) At video rates, many calculations must be performed for each input symbol without the benefit of a fast rate clock as in voice/data modems. This makes real-time decoding of video data more difficult than voice or data.
2) Data can be interleaved through multiple Trellis encoders to reduce the effect of burst noise on the received data. This means that additional processing is required on the data stream after Trellis decoding to perform de-interleaving.
3) The absence of a fast clock in a video application makes deep traceback difficult because there is a very limited number of traceback memory accesses possible during each symbol period. Techniques such as pre-traceback and multiple-symbol decoding are commonly used to address this problem.
Lin, "Area Efficient Decoders for Rate-k/n Convolutional Codes and Other High Rate Trellis Codes", U.S. Pat. No. 5,530,707, issued Jun. 25, 1996, represents one prior-art high speed trellis decoder.